#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    string reorganizeString(string barcodes) {
        unordered_map<int, int> hash;
        sort(barcodes.begin(), barcodes.end());
        int n = barcodes.size();
        int maxVal = 0;
        int maxCount = 0;
        for (int i = 0; i < n; ++i)
        {

            hash[barcodes[i]]++;
            if (maxCount < hash[barcodes[i]])
            {
                maxCount = hash[barcodes[i]];
                maxVal = barcodes[i];
            }
        }

        if (maxCount > ((n + 1) / 2))
            return "";

        int pos = 0;
        string ret;
        ret.resize(n);
        while (maxCount--)
        {
            ret[pos] = maxVal;
            pos += 2;
        }

        hash.erase(maxVal);
        for (auto& [x, y] : hash)
        {
            for (int i = 0; i < y; ++i)
            {
                if (pos >= n)
                    pos = 1;

                ret[pos] = x;
                pos += 2;
            }
        }

        return ret;
    }
};